Computing topological properties for a 3D object in 3D space is an important task in image processing [1][2]. The recent developments in medical imaging and 3D digital camera systems raise the problem of the direct treatment of digital 3D objects. In the past, 3D computer graphics and computational geometry have usually used triangulation to represent a 3D object [3][4][6][7].
Basically, the topological properties of an object in 3D contain connected components, genus of its boundary surfaces, and other homologic and homotopic properties [5]. In 3D, this problem of obtaining fundamental groups is decidable but no practical algorithm has yet been found. Therefore, homology groups have played the most significant role. Research shows that a key factor of computing homology groups of 3D objects is the genus of the boundary surface of the 3D object [3].
Theoretical results show that there exist linear time algorithms for calculating genus and homology groups for 3D Objects in 3D space [3]. However, the implementation of these algorithms is not simple due to the complexity of real data samplings. Most of the algorithms require the triangulation of the input data since it is collected discretely [3-7]. However, for most medical images, the data was sampled consecutively, meaning that every voxel in 3D space will contain data. In such cases, researchers use the marching-cubes algorithm to obtain the triangulation since it is a linear time algorithm. However the spatial requirements for such a treatment will be at least doubled by adding the surface-elements (sometimes called faces).
In this invention, we look at a set of points in 3D digital space, and our purpose is to find homology groups of the data set. The direct algorithm without utilizing triangulation was proposed by Chen and Rong in 2008 [1].
In [1], we discuss the geometric and algebraic properties of manifolds in 3D digital spaces and the optimal algorithms for calculating these properties. We consider digital surfaces as defined in [2].
We presented a theoretical optimal algorithm with time complexity O(n) to compute the genus and homology groups in 3D digital space, where n is the size of the input data [1].
The key in the algorithm in [1] is to find the genus of the closed digital surfaces that is the boundary of the 3D object. This INVENTION will provide a process that deals with simulated and real data in order to obtain the topological invariants such as connected components, boundary surface genus, and homology groups (not generators as described in [4]).